package __回溯算法

/*
*
https://leetcode.cn/problems/generate-parentheses/description/?envType=study-plan-v2&envId=top-100-liked

22. 括号生成
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：
输入：n = 1
输出：["()"]
*/
func generateParenthesis(n int) []string {
	var res []string
	gen(n, 0, 0, "", &res)
	return res
}

// left和right分别为左右括号已使用的个数，str保存字符串，res保存满足题意的所有结果
func gen(n int, left int, right int, str string, res *[]string) {
	if left == n && right == n {
		*res = append(*res, str)
		return
	}

	if left < n {
		gen(n, left+1, right, str+"(", res)
	}
	if right < n && left > right {
		gen(n, left, right+1, str+")", res)
	}
}
